package org.alg.graph;

import java.io.File;
import java.io.FileInputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
import java.util.List;

/**
 * Created by sunlei on 2015/5/2.
 */
public class BreadthFirstPaths {
    private boolean[] marked;
    private int[] edgeTo;
    private final int s;

    public BreadthFirstPaths(Graph G,int s){
        marked=new boolean[G.V()];
        edgeTo=new int[G.V()];
        this.s=s;
        bfs(G,s);
    }

    private void bfs(Graph G,int s){
        LinkedList<Integer> queue=new LinkedList<Integer>();
        marked[s]=true;
        queue.offer(s);
        while(!queue.isEmpty()){
            int v=queue.poll();
            for(int w:G.adj(v)){
                if(!marked[w]){
                    edgeTo[w]=v;
                    marked[w]=true;
                    queue.offer(w);
                }
            }
        }
    }

    public boolean hasPathTo(int v){
        return marked[v];
    }

    public Iterable<Integer> pathTo(int v){
        if(!hasPathTo(v))return  null;
        List<Integer> paths=new ArrayList<Integer>();
        for(int x=v;x!=s;x=edgeTo[x])
            paths.add(x);
        paths.add(s);
        return paths;
    }

    public void printEdgeToS(){
        for(int i=0;i<edgeTo.length;i++){
            System.out.println(i+":"+edgeTo[i]);
        }
    }

    public void printPathToV(int v){
        Iterable<Integer> path=pathTo(v);
        Iterator<Integer> it=path.iterator();
        if(path==null||it==null||!it.hasNext()) {
            System.out.println("from "+s+" to "+v+" has no way to access.");
            return;
        }
        while(it.hasNext())
            System.out.print(it.next() + "    ");
        System.out.println();
    }

    public static void main(String[] args) throws IOException {
        File f=new File("D:\\arg-data\\tinyG.txt");
        FileInputStream fis=new FileInputStream(f);
        Graph graph=new Graph(fis);
        BreadthFirstPaths bfp=new BreadthFirstPaths(graph,0);
        bfp.printPathToV(5);

        bfp.printEdgeToS();
    }
}
